\section{PSS -- Probabilistic signature scheme}

PSS je dokázateľne bezpečná (za istých predpokladov) schéma na
digitálne podpisy. Navrhli ju páni Mihir Bellare a Philip Rogaway
v \cite{pss}. Celá schéma je vlastne akýmsi znáhodnením hašovania -- k
správe sa pridá náhodný reťazec dĺžky $l_0$ a haš sa počíta až
potom. Samozrejme, pri overovaní hašu treba nejakým spôsobom
vyriešiť, aby sme sa dozvedeli použitý náhodný reťazec. Ako sa ukáže
neskôr, toto nie je až taký veľký problém ak použijeme ďalšiu
hašovaciu funkciu.

PSS má oproti doteraz spomínaným schémam jednu veľkú výhodu -- pri
dôkaze jej bezpečnosti sa ukáže ``tesná'' hranica. T.j., možnosť
prelomiť PSS s pravdepodobnosťou $\eps$ priamo umožňuje lámanie RSA s
rovnakou pravdepodobnosťou.


\subsubsection{RSA-PSS}

Podpisová schéma $PSS[l_0,l_1]=\langle GenPSS,SignPSS,VerifyPSS\rangle$ je
schéma s kľúčom dĺžky $k$ parametrizovaná dvoma hodnotami $k_0, k_1$.
Generovanie kľúča dĺžky $k$ je presne rovnaké ako v $GenRSA\mbox{-}FDH$.

Pri podpisovaní bude náš algoritmus používať dve hašovacie funkcie.
Prvú si označíme $h$ a nazveme ju kompresor, pretože bude skracovat
správu, $h:\{0,1\}^* \rightarrow \{0,1\}^{k_1}$.
Druhá funkcia bude $g$ (nazvaná aj generátor), pričom
$g:\{0,1\}^{k_1} \rightarrow \{0,1\}^{k-k_1-1}$.

Ešte si označíme $g_1$, resp. $g_2$ ako funkciu, ktorá vracia
prvých $l_0$ (resp. zvyšných $k-k_0-k_1-1$) bitov funkcie $g$.

\begin{figure}[h]
    \centering
    \includegraphics{img/02/pss.1.mps}
    \caption{Postup podpisovania v schéme PSS}
    \label{fig:pss}

\end{figure}
Na obrázku \ref{fig:pss} je schematicky naznačený postup podpisovania
podľa pseudokódu \ref{proc:signpss}

% {{{ proc SignPSS
\begin{procedure}
    \caption{SignPSS($m$)}
    \label{proc:signpss}
    $r \inr \{0,1\}^{k_0}$\;
    $w \assign h(M \concat r)$\;
    $r^* \assign g_1(w) \xor r$\;
    $y \assign 0 \concat w \concat r^* \concat g_2(w)$\;
    \Return $y^d \bmod N$\;
\end{procedure}
%% }}}

Môžeme si všimnúť, že náhodný reťazec $r$ sme neuviedli v
``otvorenom'' tvare, ale zviazali sme ho (prexorovaním) funkciou $g_1$. 
Intuitívne,
toto nám umožní zaručiť jeho integritu a zároveň máme možnosť ho
zrekonštruovať.

Overovanie podpisu je popísané v pseudokóde \ref{proc:verifypss}

%%% {{{ proc VerifyPSS
\begin{procedure}
    \caption{VerifyPSS($m$,$x$)}
    \label{proc:verifypss}
    $y \assign x^e \bmod N$\;
    rozdeľ $y$ na $b \concat w \concat r^* \concat \gamma$\;
    $r \assign r^* \xor g_1(w)$\;
    \eIf{$(b \ne 0) \vee (g_2(w) \ne \gamma) 
            \vee (h(m \concat r) \ne w)$}
    {% then
        \Return reject\;
    }{% else
        \Return accept\;
    }
\end{procedure}
%%% }}}

\todo{nejake omacky okolo funkcnosti a preco je  to zhruba tak
spravene}

\subsubsection{Dôkaz bezpečnosti}
\todo{dokaz bezpecnosti - tesna redukcia}
